package quick_sort

func quickSort(vals []int, left, right int) {
	val := vals[left]
	pos := left
	i, j := left, right

	for i <= j {
		for j >= pos && vals[j] >= val {
			j--
		}

		if j >= pos {
			vals[pos] = vals[j]
			pos = j
		}

		for i <= pos && vals[i] <= val {
			i++
		}

		if i <= pos {
			vals[pos] = vals[i]
			pos = i
		}
	}

	vals[pos] = val

	if pos-left > 1 {
		quickSort(vals, left, pos-1)
	}

	if right-pos > 1 {
		quickSort(vals, pos+1, right)
	}

}

func QuickSort(vals []int) {
	quickSort(vals, 0, len(vals)-1)
}
